#ifndef DOUBLELINKEDLIST_H
#define DOUBLELINKEDLIST_H


template <typename DT>
class DoubleLinkedList{
    private :
        
        /// @brief 节点Node类型声明
        struct Node{

            DT data;        //存储节点内的数据
            Node *prev;     //指向上一节点的指针
            Node *next;     //指向下一节点的指针

            
            /// @brief 节点的构造函数
            /// @param d 节点的数据
            /// @param p 指向下一节点的指针，缺省值为nullptr
            /// @param n 指向上一节点的指针，缺省值为nullptr
            Node( const DT & d = DT{},Node *p = nullptr,Node *n = nullptr):
                data{d},prev{p},next{n}{}

            Node( DT && d,Node *p = nullptr, Node *n = nullptr):
                data{std::move(d)},prev{p},next{n}{} 

        };

    public:

        //const_iterator类
        class const_iterator{
            public:

                /// @brief const_iterator的构造函数，初值设为nullptr
                const_iterator():current{nullptr}{}

                /// @brief 重载运算符*
                /// @return 返回迭代器指向的节点的数据引用
                const DT & operator*()const
                {
                    return retrieve();
                }

                /// @brief 重载运算符++（前缀），将当前迭代器值+1
                /// @return 返回+1后的迭代器值
                const_iterator & operator++()
                {
                    current = current -> next;
                    return *this;
                }

                /// @brief 重载运算符++（前缀），将当前迭代器值+1
                /// @return 返回+1前的迭代器值
                const_iterator operator++(int)
                {
                    const_iterator old = *this;
                    ++(*this);
                    return old;
                }

                /// @brief 重载运算符 == ，比较两个迭代器值是否相同
                /// @param rhs 另一个迭代器值
                /// @return 若两个迭代器值相同，返回true，否则返回false
                bool operator==(const const_iterator & rhs)const
                {
                    return current == rhs.current;
                }

                /// @brief 重载运算符 != ，比较两个迭代器值是否相同
                /// @param rhs 另一个迭代器值
                /// @return 若两个迭代器值不同，返回true，否则返回false
                bool operator!=(const const_iterator & rhs)const
                {
                    return !(*this == rhs);
                }

            
            protected:
               
                /// @brief const_iterator的数据域为指向一个Node的指针
                Node *current;
                
                /// @brief 获得当前指向Node的Data
                /// @return 返回current指向的Node的Data的引用
                DT & retrieve() const
                {
                    return current -> data;
                }



                /// @brief const_iterator的有参构造函数
                /// @param p 指针
                const_iterator(Node *p):current{p}{}

                friend class DoubleLinkedList<DT>;  ///赋予List类访问const_iterator的非公有成员的权利
        };

        /// @brief iterator类的声明与实现，其继承了const_iterator类
        class iterator: public const_iterator
        {
            public:
                
                /// @brief iterator类的构造函数
                iterator(){}
                
                /// @brief 重载运算符*
                /// @return 返回迭代器指向的节点的数据引用
                DT & operator*(){
                    return const_iterator::retrieve();
                }
                const DT & operator*()const{
                    return const_iterator::operator*();
                }

                /// @brief 重载运算符++（前缀），将当前迭代器值+1
                /// @return 返回+1后的迭代器值
                iterator & operator++(){
                    this -> current = this -> current -> next;
                    return *this;
                }

                /// @brief 重载运算符++（前缀），将当前迭代器值+1
                /// @return 返回+1前的迭代器值
                iterator operator++ (int){
                    iterator old = *this;
                    ++(*this);
                    return old;
                }

                protected:
                    
                    /// @brief iterator的有参构造函数
                    /// @param p 输入的指针参数
                    iterator(Node *p):const_iterator{p}{}
                    
                    friend class DoubleLinkedList<DT>;
        };
    
    public:

        /// @brief List的无参构造函数
        DoubleLinkedList()
        {
            init();
        }
        
        /// @brief List的拷贝构造函数
        /// @param rhs 已有的List的引用
        DoubleLinkedList(const DoubleLinkedList & rhs)
        {
            init();
            for(auto &x : rhs)
                push_back(x);
        }
        
        /// @brief List的移动构造函数
        /// @param rhs 
        DoubleLinkedList(DoubleLinkedList && rhs):theSize{rhs.theSize},head{rhs.head},tail{rhs.tail}
        {
            rhs.theSize = 0;
            rhs.read = nullptr;
            rhs.tail = nullptr;
        }
        
        
        /// @brief List类的析构函数
        ~DoubleLinkedList()
        {
            clear();
            delete head;
            delete tail;
        }
        
        /// @brief List类的拷贝赋值运算符=
        /// @param rhs 要赋给被赋值对象的对象
        /// @return 被赋值对象的引用
        DoubleLinkedList & operator=(const DoubleLinkedList & rhs)
        {
            DoubleLinkedList copy = rhs;
            std :: swap(*this,copy);
            return *this;
        } 


        /// @brief List类的移动赋值运算符=
        /// @param rhs 要赋给被赋值对象的对象
        /// @return 被赋值对象的引用
        DoubleLinkedList & operator=(DoubleLinkedList && rhs)
        {
            std::swap(theSize,rhs.theSize);
            std::swap(head,rhs.head);
            std::swap(tail,rhs.tail);

            return *this;
        }

        /// @brief 得到List的头端标记
        /// @return 返回List的head节点后的第一个节点的迭代器值
        iterator begin(){
            return {head -> next};
        }
        const_iterator begin() const{
            return {head -> next};
        }

        /// @brief 得到List的尾端标记
        /// @return 返回List的tail节点（最后一项之后的一个节点）的迭代器值
        iterator end(){
            return {tail};
        }
        const_iterator end() const{
            return {tail};
        }

        /// @brief 获得List的大小
        /// @return 返回List的节点数（theSize值）
        int size() const{
            return theSize;
        }

        /// @brief 判断List是否为空
        /// @return 若List为空返回true，否则返回false
        bool empty() const{
            return size()==0;
        }

        /// @brief 清空List
        void clear(){
            while(!empty())
                pop_front();
        }

        /// @brief 得到List头端节点的值
        /// @return 返回List的head节点的后一节点的数据的引用
        DT & front(){
            return *begin();
        }
        const DT & front() const{
            return *begin();
        }

        /// @brief 得到List尾端节点的值
        /// @return 返回List的tail节点的后一节点的数据的引用
        DT & back(){
            return *--end();
        }
        const DT & back() const{
            return *--end();
        }

        /// @brief 新增数据于List的最前端
        /// @param x 新增的数据
        void push_front(const DT &x){
            insert(begin(),x);
        }
        void push_front(DT && x){
            insert(begin(),std::move(x));
        }


        /// @brief 新增数据于List的最后端
        /// @param x 新增的数据
        void push_back(const DT & x){
            insert(end(),x);
        }
        void push_back(DT && x){
            insert(end(),std::move(x));
        }

        /// @brief 将List的最前端节点删除
        void pop_front(){
            erase(begin());
        }

        /// @brief 将List的最后端节点删除
        void pop_back(){
            erase(--end());
        }

        /// @brief 插入一个新的节点于给定位置前
        /// @param itr 给定的位置
        /// @param x 插入的节点的值
        /// @return 返回新插入的节点的迭代器值
        iterator insert(iterator itr, const DT & x)
        {
            Node *p = itr.current;
            theSize++;
            return {p -> prev = p -> prev -> next = new Node{x, p -> prev, p}};
        }
        iterator insert(iterator itr, DT && x){
            Node *p = itr.current;
            theSize++;
            return {p -> prev = p -> prev -> next = new Node{std::move(x), p -> prev, p}};
        }
        
        /// @brief 删除itr对应的节点
        /// @param itr 给定的位置
        /// @return 返回被删除节点的后一节点的迭代器值
        iterator erase(iterator itr)
        {
            iterator check = begin();
            while(check != itr && check != end()) check++;

            if(check == itr){
                Node *p = itr.current;
                iterator retVal{p -> next};
                p -> prev -> next = p -> next;
                p -> next -> prev = p -> prev;
                delete p;
                theSize--;
                return retVal;
            }else{
                return itr;
            }
            
        }

        /// @brief 将from至to（不含）间的节点全部删除
        /// @param from 删除的起始节点
        /// @param to 删除的最后节点（不含）
        /// @return 返回to节点的迭代器值
        iterator erase(iterator from, iterator to)
        {
            for(iterator itr = from; itr != to;)
                itr = erase(itr);

            return to;
        }
    
    private:
        int theSize;    /// List的长度
        Node *head;     /// List的头节点
        Node *tail;     /// List的尾节点

        /// @brief 生成并初始化一个只含有head和tail的空链表
        void init()
        {
            theSize = 0;
            head = new Node;
            tail = new Node;
            head -> next = tail;
            tail -> prev = head;
        }
};

#endif